package com.zhupf.part7;

/**
 * @author zhupf
 * @date 2023年11月23日 10:24
 * @Description 23、合并k个升序链表
 */
public class MergeKLists {

    public static void main(String[] args) {
        ListNode l1 = new ListNode(1,new ListNode(4,new ListNode(5)));
        ListNode l2 = new ListNode(1,new ListNode(3,new ListNode(4)));
        ListNode l3  = new ListNode(2,new ListNode(6));
        ListNode[] lists = {l1,l2,l3};
        ListNode listNode = mergeKLists2(lists);
        System.out.println("结束");
    }

    public static ListNode mergeKLists2(ListNode[] lists) {
        if(lists == null || lists.length == 0){
            return null;
        }
        return merge(lists,0,lists.length-1);
    }

    public static ListNode merge(ListNode[] lists , int begin,int end){
        if(begin == end ){
            return lists[begin];
        }
        int mid = end-(end-begin)/2;
        ListNode beginNode = merge(lists,begin,mid-1);
        ListNode endNode = merge(lists,mid,end);
        return mergeListNode(beginNode,endNode);
    }

    public static ListNode mergeListNode(ListNode node1 , ListNode node2){
        ListNode pre = new ListNode(0);
        ListNode node = pre;
        while (node1 != null && node2 != null){
            if(node1.val<node2.val){
                node.next = node1;
                node1 = node1.next;
            }else {
                node.next = node2;
                node2 = node2.next;
            }
            node = node.next;
        }
        pre.next = node1 == null?node2:node1;
        return pre.next;
    }


    public static ListNode mergeKLists(ListNode[] lists) {
        if(lists == null || lists.length == 0){
            return null;
        }
        if(lists.length == 1){
            return lists[0];
        }
        int mid = lists.length/2;
        ListNode[] left = new ListNode[mid];
        ListNode[] right = new ListNode[lists.length-mid];
        for (int i = 0 ; i < mid ; i ++){
            left[i] = lists[i];
        }
        for (int i = lists.length-1 ; i >= mid ; i --){
            right[i-mid] = lists[i];
        }
        ListNode leftNode = mergeKLists(left);
        ListNode rightNode = mergeKLists(right);
        ListNode merge = merge(leftNode, rightNode);
        return merge;
    }

    public static ListNode merge(ListNode head1 , ListNode head2){
        ListNode dumy = new ListNode(0);
        ListNode pre = dumy;
        while (head1 != null && head2 != null){
            if(head1.val <= head2.val){
                pre.next = head1;
                head1= head1.next;
            }else {
                pre.next = head2;
                head2 = head2.next;
            }
            pre = pre.next;
        }
        pre.next = head1 == null? head2:head1;
        return dumy.next;
    }


    static class ListNode {
        int val;
        ListNode next;
        ListNode() {
        }
        ListNode(int val) {
            this.val = val;
        }
        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

}
